package com.lmz.project.redis.arithmetic.master;

/**
 * master 公式 T(N) = a * T(N/b) + O(N^c)  a、b、c都是常数
 * 注意：这个公式只能适用于子问题等规模的情况
 * 如果log(b,a) < c 复杂度为 ： O(n^c);
 * 如果log(b,a) > c 复杂度为 ： O(n^log(b,a));
 * 如果log(b,a) = c 复杂度为 ： O(n^c * logn);
 * 补充
 * T(n) = 2* T(n/2) + O(n * logn) 时间复杂度是O(n * ((log n)的平方))，
 */
public class MasterEquation {


    public static void main(String[] args) {
        int[] arr = {4, 2, 6, 1};
        int f = f(arr, 0, arr.length - 1);
        System.out.println(f);
    }

    //arr[l....r] 范围上的最大值
    public static int f(int[] arr, int l, int r) {
        if (l == r) {
            return arr[l];
        }
        int mid = l + (r - l) / 2;
        int lmax = f(arr, l, mid);
        int rmax = f(arr, mid + 1, r);
        return Math.max(lmax, rmax);
    }
}
